14.8 並列圧縮
マークに加え移動も並列に行う
並列スライディングコンパクションでヒープが連続しているなら少し簡単
順序が保存される
マークフェーズが終われば移動先が確定するため，移動時の競合は性能が劣化するだけで整合性は保たれる（微妙では？）
C++的にはだめ
一般にはマークの後再配置先を計算するフェーズを追加することになる
論理型プログラミング言語 Parlog のための location-aware (≒ スライディングコンパクション) 並列コレクタ (Crammond 1998)
論理型プログラミング言語ではヒープ順が保たれていると嬉しい
「チョイスポイント」へのバックトラックが効率的にできるため
チョイスポイントは多分場合分けの地点で，行き先で単一化に失敗したらバックトラックする仕組みがある
バックトラックするとき，戻るチョイスポイント以降の番地のオブジェクトを全部破棄すればよい
スレッデッドコレクタ (3.3 節) の並列化版
ヒープを小領域に分割し，プロセッサに割り当てる
マーク時の処理：
マーク自体は自分の小領域だけに対して行うのではなく別のポリシーで行われている？
自分の小領域にオブジェクトを発見したら単にマークするだけ
リモートオブジェクト(=自分の小領域外のオブジェクト)なら，そのオブジェクトへの参照を担当するプロセッサの間接参照のスタックに積んで，グローバルなカウンタをインクリメント
担当のプロセッサはスタックを見て処理，カウンタをデクリメント
間接参照はマークされたオブジェクトの1%に満たないほど少ないので効率的だという主張らしい
Flood et al による JVM の年少世代向け並列マークコンパクトGC
並列マークの後に以下の3つを行う：
(1) 転送アドレス計算
(2) 参照の更新
(3) オブジェクトの移動
フェーズごとに異なる負荷分散の戦略が用いられる
以降スレッド数を $ N とする
(1) 転送アドレス計算
各オブジェクトのヘッダに転送先アドレスを書き込む
空間を（オブジェクトを分割しないように注意しながら）細かく均等な区画に分割する
$ 4N 個ぐらいにすると早いらしい
各スレッドは分割された区画を奪い合う
獲得した領域で生きているオブジェクトをカウント
これと同時に，ゴミオブジェクトを結合して1つの準オブジェクトにする
各区画の生存オブジェクトのサイズを元に，ヒープを各小領域 (!= 区画) がほぼ同じ量の生きているオブジェクトを含むように，不均一な $ N 個の小領域に分割 (小領域はいくつかの区画からなる)
空間を（区画単位で）左から少しずつ見ていって，$ size / Nぐらいになったら切るみたいなイメージだと思う
同時に各区画で最初の生きているオブジェクトの行き先アドレスを計算
その区画が属する小領域はわかるので可能
最後に各区画単位でスレッドが競争して，全部の行き先アドレスを計算
(2) 参照の更新
圧縮対象の空間にあるオブジェクトが持つポインタ以外についても考慮しないといけない
圧縮対象の空間（例えば年長世代）を区画によって分割して更新
年少世代の空間については単一タスクとして走査
なんで単一タスク？例えば (3) 移動フェーズの後ろで動いていてもいいので，時間をかけてもよいから？
(3) 移動フェーズ
ヒープの端に全部のオブジェクトを寄せない
転送アドレス計算で分割された $ N個の小領域それぞれにコンパクションスレッドを割り当てる
各スレッドが，オブジェクトをその小領域の端に集める
偶奇で左右のどちらに寄せるかを切り替える．図を見れば一瞬でわかるので説明は省略
多少の断片化は諦める
https://gyazo.com/a0cf8ca9bfa9e320d2788045ac490bb9
欠点：
欠点1：ヒープを処理するパスが3つあること
欠点2：空き領域が$ \lceil (N+1)/2 \rceilに分かれてしまうこと
Abuaiadh et al らによる上記の手法の欠点の改善
欠点1への対処
転送アドレスを書き込むのをやめる(phase2 をなくす)
代わりにマークビットマップとオフセットベクタを用いて転送アドレスを計算
オフセットベクタは各ブロックの生きているオブジェクトの新しいアドレスを保持
欠点2への対処
ヒープを比較的大きな小領域に（プロセッサ数に対して）過剰に分割する
例えばプロセッサ数の16倍に分割するとか
これらの小領域を順番に圧縮
各小領域の空き領域の先頭へのポインタを保持する表を作成
スレッドがグローバルな小領域のインデックスを不可分にインクリメントして競争して小領域を獲得
つまり小領域の獲得は wait-free
獲得したスレッドが小領域の圧縮の責任を持つ
競争に勝ったスレッドは，次は移動先の小領域をめぐり競争する
移動先の小領域の選び方は，詰めたい方向の小領域を狙いに行く
表の対応するスロットに atomic に null を書き込もうとする
表のエントリが null ならその小領域を移動先・移動元にしない
移動元？：別のスレッドによって自身が移動先の小領域として選択されるような状況では，自身より前が埋まっているはず
よってその小領域は動かす必要がないので仕事を放棄する
オブジェクトが小さい番号の小領域から大きい番号の小領域に移動させることもない
そういう場合はそもそも動かす必要がないので（自身より前が全部 full だから）
最悪の場合でも，オブジェクトは自身が属する領域にはオブジェクトを移動させられるため進行性は保証される
ある小領域の圧縮が完了すると，表に記録した空き小領域へのポインタを更新
新しい空き領域の先頭
もしその小領域がいっぱいなら null のままにしておく
よくわかってないが，このやり方だと前の方の小領域に細かい断片化は発生しうるはず
ただし，前の方は基本的に密にはなってくれる
後ろの方にそれなりに大きい塊ができるのだから，それで良かろうという主張だろうと推測しています
オブジェクトの移動についての別の方法
圧縮の質を落とす代わりに圧縮にかかる時間を短縮する方法
オブジェクト単位ではなく，ブロック（例えば 256byte の塊）をまるごと移動する
ブロック内部では圧縮しない
ただし，全く圧縮できないようなケースも簡単に作れてしまう
コンプレッサ (Kermany and Petrank, 2006)
転送アドレスを格納するのではなく計算するアプローチを採用
Abuaiadh の方法をより修正したもの
違い1：2つ目のフェーズでマークビットマップを操作するとき，ファーストオブジェクトベクタも追加で作る
オブジェクトの移動先となるページでインデックスされるベクタ
4Kbyte / ページのやつ
各スロットには，そのページに移動する最初のオブジェクトの from 空間でのアドレスを記録
first_object_vector[index] = addr_in_from
圧縮処理は，ルート集合を更新することから始まる
としか書いてないのでまあ適当にふーんということにしておく
違い2：to 空間のページをファーストオブジェクトベクタから取得することをめぐって争う
成功したスレッドは取得した仮想ページに対し物理ページを割り当てる
違い1の段階では，to 空間の物理ページは決まってない
ファーストオブジェクトベクタのスロットで指定された場所を起点として，オフセットベクタとマークベクタを使いながら順にオブジェクトをコピー
オブジェクトの退避先として新しいページを取得することで，コレクタの並列化を可能とする
コピーGCっぽくみえるが，真にスライディングを行うマークコンパクトGCである
典型的にはスレッドごとにわずか1ページの実メモリしか余計に使わずに from 空間と to 空間を管理する
新しい to 空間のページをマップする必要はあるが，それと同時に，生きているオブジェクトをすべて退避させ終えた from 空間のページをアンマップできることが効いている
圧縮処理を行うスレッド間の同期は最小限になっている
オブジェクトの移動先となる，ファーストオブジェクトテーブルのスロット取得の際に同期が必要
ページをまたがるオブジェクトの扱いは難しい
ストップザワールドなら，そのようなオブジェクトは to 空間の中で移動先となる最初のページに属すると勝手に決めれば済む
並行GC だとこれではだめ（17.7 節でまたやるらしい）